1. Field of the Invention
This invention relates generally to the field of automated design techniques for electronic circuits, and more specifically to compaction methods and systems for hierarchically defined layouts of integrated circuits.
2. Related Art
Layout compaction is the process of taking an existing layout and producing a new layout in which some geometrical aspect (usually size) is minimized. This process preserves the underlying circuit integrity and enforces design rule correctness. The constraints that need to be satisfied during compaction give rise to a system of linear inequalities. For the compaction of layouts devoid of hierarchy, this constraint system can be solved efficiently using graph based techniques. For compaction of multi-level hierarchies in which cell abutment is to be preserved, the system of constraints is more complex and must be solved using general linear programming (LP) techniques. Because of the computational complexity of LP, it is imperative to keep the number of variables and constraints to a minimum.
Objects within a cell that interact with objects in other cells are called ports. In order to reduce the number of variables and constraints that need to be solved by LP a port abstraction is used for each cell. This abstraction consists of the ports of the cell and the constraints between them induced by the internals of the cell. Only the variables representing the ports and the constraints between them need to be solved by LP. The number of ports is small compared to the total number of objects in the cell. The number of constraints between the ports is typically on the order of the number of ports. Therefore the size of the problem that needs to be solved by LP is considerably reduced.
Over-the-cell routing (OTCR) is a means by which cells can be personalized at higher levels of the hierarchy. Through its use, a same cell can be tailored to fit several different requirements. OTCR commonly is used in regular structures such as PLAs, data paths, etc. OTCR consists of primitive objects placed on top of instances and generally is used to connect objects in the interior of an instance to the outside, as well as to connect objects within an instance.
OTCR objects occurring over an instance interact with objects inside that instance. These objects must then become ports of the master cell of that instance. Hence, the variables representing their locations and the constraints between them need to be solved using linear programming. FIG. 1 shows a cell A containing ten contacts 100. An OTCR wire 102 over A is shown across cell A. Because this OTCR object 102 requires a design rule spacing to each of the contacts 100, all ten contacts must become ports of cell A.
In the absence of OTCR, all the ports are on the boundary of the cell. Hence, the number of ports relative to the number of objects in the cell is small. Also, this proportion decreases as the size of the cell increases. In the presence of OTCR this proportion can be large and does not always decrease as cell size increases. OTCR objects, such as buses that run over instances, can interact with a large number of objects in a cell, causing almost all the objects in the cell to become ports. Furthermore, a same cell can be instantiated with several different patterns of OTCR. All the objects in the cell that interact with any of these patterns anywhere in the hierarchy must become ports.
Most commonly occurring hierarchies contain some amount of OTCR. Any effective hierarchical compaction method must incorporate a strategy for handling OTCR without significantly degrading the performance. In the presence of OTCR, the compactor must preserve design rule correctness and circuit integrity across levels of the hierarchy whilst preserving input hierarchy and cell abutment.
True hierarchical compaction maintains the input layout hierarchy as well as the abutment constraints between cells. The bottleneck for hierarchical compaction is the time taken to analyze the system of equations which must be solved via linear programming methods. Because of the computational complexity of linear programming, it is essential to keep this system of equations as small as possible. In the presence of OTCR the amount of interaction between levels of hierarchy increases considerably. This causes a substantial rise in the number of constraints and hence the time taken by the compaction process is significantly increased.
Thus, there remains a need for an efficient compaction system and method for arbitrary hierarchies containing over-the-cell routing without significantly degrading the run time performance of the hierarchical compactor.